#include<iostream>
using namespace std;
#include<vector>
#include<list>
#include<algorithm>


 //struct ListNode {
 //  int val;
 //   ListNode *next;
 //   ListNode() : val(0), next(nullptr) {}
 //    ListNode(int x) : val(x), next(nullptr) {}
 //  ListNode(int x, ListNode *next) : val(x), next(next) {}
 //};
 
 //class Solution {
 //public:
 //    ListNode* deleteDuplicates(ListNode* head) {
 //        ListNode* prev = new ListNode();
 //        ListNode* cur = head;
 //        ListNode* next = nullptr;
 //        int flag = 0;
 //        while (cur)
 //        {
 //            next = cur->next;
 //            int value = cur->val;
 //            if (next && next->val == value)
 //            {
 //                while (next && next->val == value)
 //                {
 //                    if (cur == head) flag = 1;
 //                    delete cur;
 //                    cur = next;
 //                    next = cur->next;
 //                    delete cur;
 //                }
 //                prev->next = next;
 //                cur = next;
 //                if (flag == 1)
 //                {
 //                    head = cur;
 //                    flag = 0;
 //                }
 //            }
 //            else
 //            {
 //                prev = cur;
 //                cur = cur->next;
 //            }

 //        }
 //        return head;
 //    }
 //};
// class Solution {
//public:
//    string Add(string& s1, string& s2)
//    {
//        int extra = 0;
//        string ret;
//        int length = max(s1.size(), s2.size());
//        for (int i = 0; i < length; i++)
//        {
//            int num1 = i >= s1.size() ? 0 : s1[i];
//            int num2 = i >= s2.size() ? 0 : s2[i];
//
//            int num = num1 + num2 + extra;
//            ret += num % 10;
//            extra = num / 10;
//        }
//        if (extra) ret += 1;
//        return ret;
//    }
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//        string s1,s2;
//        ListNode* cur1 = l1;
//        ListNode* cur2 = l2;
//        while (cur1)
//        {
//            s1 += (cur1->val);
//            cur1 = cur1->next;
//        }
//        while (cur2)
//        {
//            s2 += (cur2->val);
//            cur2 = cur2->next;
//        }
//        //reverse(s1.begin(),s1.end());
//        //reverse(s2.begin(), s2.end());
//        string s = Add(s1, s2);
//
//        //reverse(s.begin(), s.end());
//        ListNode* head = new ListNode();
//        ListNode* cur = head;
//        for (auto e : s)
//        {
//            ListNode* nextnode = new ListNode(e);
//            cur->next = nextnode;
//            cur = nextnode;
//        }
//        return head->next;
//    }
//};
// int main()
// {
//     int a1[] = { 8,7,6 };
//     int a2[] = { 3,2,1 };
//     ListNode* head1 = new ListNode();
//     ListNode* cur = head1;
//
//    for (auto e : a1)
//    {
//        ListNode* next = new ListNode(e);
//        cur->next = next;
//        cur = next;
//    }
//
//    ListNode* head2 = new ListNode();
//    cur = head2;
//
//    for (auto e : a2)
//    {
//        ListNode* next = new ListNode(e);
//        cur->next = next;
//        cur = next;
//    }
//    Solution s;
//    s.addTwoNumbers(head1->next, head2->next);
//    return 0;
// }
//int main()
//{
//    int a[] = { 1,1,1,2,3 };
//    ListNode* head = new ListNode();
//    ListNode* cur = head;
//
//    for (auto e : a)
//    {
//        ListNode* next = new ListNode(e);
//        cur->next = next;
//        cur = next;
//    }
//    Solution s;
//    ListNode* newhead = s.deleteDuplicates(head->next);
//    while (newhead)
//    {
//        cout << newhead->val << endl;
//        newhead = newhead->next;
//    }
//    return 0;
//}



